In the digital video broadcast via satellite standard DVB-S2, a low-density parity-check LDPC algorithm is used for error correction, i.e. to transmit a message over a noisy transmission channel. The LDPC is a code allowing a data transmission rate closed to the theoretical maximum. The LDPC codes are defined as a sparse parity-check matrix which can be randomly generated. The LDPC decoding can be implemented in the standards IEEE 802.11n and IEEE 802.16e. In “Low cost LDPC decoder for DVB-S2”, DATE Designers Forum 2006, pages 130-135, a LDPC decoder based on barrel shifters has been described.
FIG. 1 shows a basic diagram of an architecture of a LDPC decoder according to the prior art. Here, an IO controller IOC, an address generator AG, a barrel shifter BS, a first memory unit M1, a second memory unit M2 and several data paths DP0, DP1, DPD1 are depicted. D data words αn are packed into one word in the α memory M1. These αn words are rotated over a certain angle by means of the barrel shifters BS and passed on to the D data paths. After Km clock cycles, the αn words are returned and are rotated back over the same angle.
Accordingly, a barrel shifter is used to shift a data word by a specific number of positions. It can for example be implemented as a sequence of multiplexers. The output of one multiplexer is connected to the input of the next multiplexer depending on the shift distance. The number of multiplexers required is n*log2 (n) with n bit words. In a four bit barrel shifter with inputs A, B, C and D, the barrel shifter can cycle the order of the bits A, B, C, D, i.e. the shifter can shift all the outputs up to three positions to the right. Typically, a barrel shifter is implemented as a cascade of parallel 2×1 multiplexers. In case of a four bit barrel shifter, an intermediate signal is used to shift by two bits or passes the same data.
In “A new design for a fast barrel switch network”, by Tharakan et al. in IEEE Journal of Solid-state circuits, volume 27, no. 2, February 1992, a barrel shifter is described.
FIG. 2 shows a schematic block diagram of a barrel shifter according to the prior art. The barrel shifter comprises several layers each comprising a plurality of multiplexers. Each multiplexer has two inputs and an output. The first layer L1 of the barrel shifter rotates the input vector over [0,1], the second layer L2 rotates the input vector over [0,2], the third layer rotates the input vector over [0,4]. By combining the layers, any desired shift angle can be achieved. The barrel shifter according to FIG. 2 should however not only able to rotate the input vector over the parallelism factor n but also over smaller instances. Here, a barrel shifter of n=8 is depicted.
FIG. 3 shows a schematic block diagram of a barrel shifter according to the prior art. In FIG. 3, a barrel shifter with n=6 is depicted.
FIG. 4 shows a schematic block diagram of a further barrel shifter according to the prior art. In particular, the barrel shifter according to FIG. 4 is a combination of the barrel shifters of FIG. 2 and FIG. 3. The barrel shifter according to FIG. 4 furthermore constitutes a configurable barrel shifter. However, the multiplexing tree increases with x−1, wherein x being the number of tap points. The number of multiplexing trees is the number of the vertical wires which is P−1 for P=2a, wherein a>1. For the case that P is not a power of two, the next power of two must be used. The complexity of this network is thus ≧P*x.
The current bit of the last multiplexer in the layer L1 is forwarded to the first input of the first multiplexer in the first layer L1. At the last multiplexer in the second layer L2, the output of the last multiplexer in the first layer is inputted as the second input. The first input of the multiplexer of the last multiplexer of the second layer corresponds to the output of the second but last multiplexer in the first layer. The last multiplexer in the third layer L3 receives at its second input the output of the last multiplexer in the second layer L2 and at its first input is the output of the fourth multiplexer of the second layer L2.
In FIG. 4, the barrel shifter can be operated either at n=6 or at n=8. Accordingly, at the output of each layer, a multiplexer MUXL1, MUXL2, MUXL3, respectively is arranged and receives the sixth input bit and the eighth input bit.
For an IEEE 802.16e architecture, the parameters of such a barrel shifter are n=96 and x=19. Accordingly, the barrel shifter has a complexity of 7*96=673. If such a barrel shifter has to be made configurable, then the complexity is 18*673=1728 increasing the complexity by 250%. Furthermore, if the barrel shifter is to be made fully configurable, the complexity will raise from n*log (n) to n2+nlog (n). A logic depth of the barrel shifters according to the state of the art corresponds to the traditional log(n) and the additional selection tree of log(x). If x=n, this factor is 2.